#include <iostream>

using namespace std;

/**
 * 链表第n个节点 n 是从0开始， n > 0, n < size
 * 维护了一个虚拟头节点，当链表为空时 则只有一个虚拟头节点
 * current 每次移动从第0个元素开始
 * 
 */
class MyLinkedList {
public:
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(): val(0), next(nullptr) {};
        LinkedNode(int x): val(x), next(nullptr) {};
        LinkedNode(int x, LinkedNode* next): val(x), next(next) {};
    };

    MyLinkedList() {
        beforeHead = new LinkedNode();
        size = 0;
    }
    
    int get(int index) {
        if (index < 0 || index > size - 1) {
            return -1;
        }

        LinkedNode* current = beforeHead->next;
        while (index--) {
            current = current->next;
        }

        return current->val;
    }

    void addAtHead(int val) {
        LinkedNode* temp = new LinkedNode(val);
        temp->next = beforeHead->next;
        beforeHead->next = temp;
        size++;
    }

    void addAtTail(int val) {
        LinkedNode* current = beforeHead;
        while (current->next != nullptr) {
            current = current->next;
        }

        current->next = new LinkedNode(val);
        size++;
    }

    // 保证 current->next 为第n个节点 那么在 current 后面添加节点就好了
    void addAtIndex(int index, int val) {
        if (index < 0 || index > size) {
            return;
        }

        LinkedNode* current = beforeHead;
        while (index--) {
            current = current->next;
        }

        LinkedNode* temp = new LinkedNode(val);
        temp->next = current->next;
        current->next = temp;
        size++;
    }

    // 保证 current->next 为第n个节点 那么在删除 current-next 节点就好了
    void deleteAtIndex(int index) {
        if (index < 0 || index > size - 1) {
            return;
        }
        LinkedNode* current = beforeHead;
        while (index--) {
            current = current->next;
        }

        LinkedNode* temp = current->next;
        current->next = current->next->next;
        delete temp;
        temp = nullptr;
        size--;
    }

    void printListNode() {
        cout << "int myLinkList: ";
        LinkedNode* current = beforeHead->next;
        while (current != nullptr) {
            cout << current->val << " ";
            current = current->next;
        }
        cout << "\n";
    }
private:
    int size{};
    LinkedNode* beforeHead;
};

int main() {
    MyLinkedList* obj = new MyLinkedList();
    obj->printListNode();

    obj->addAtHead(7);
    obj->printListNode();

    obj->addAtHead(2);
    obj->printListNode();

    obj->addAtHead(1);
    obj->printListNode();

    obj->addAtIndex(3, 0);
    obj->printListNode();

    obj->deleteAtIndex(2);
    obj->printListNode();

    obj->addAtHead(6);
    obj->printListNode();

    obj->addAtTail(4);
    obj->printListNode();

    cout << "get: " << obj->get(4) << "\n";
    obj->printListNode();

    obj->addAtHead(4);
    obj->printListNode();

    obj->addAtIndex(5, 0);
    obj->printListNode();

    obj->addAtHead(6);
    obj->printListNode();

    return 0;
}